package day06;

import java.util.ArrayList;
import java.util.Scanner;

public class Test05 {
	/*
	 * 题目：有一个已经排好序的数组。
	 * 现输入一个数，要求按原来的规律将它插入数组中。
	程序分析：首先判断此数是否大于最后一个数，然后再考虑插入中间的数的情况，插入后此元素之后的数，依次后移一个位置。

	 * */
public static void main(String[] args) {
	
	//定义一个数组用于查询位置
	//定义集合用于添加元素
	int[] arr=new int[] {1,5,10,20,21,25};
	//将arr数组添加到list集合
	ArrayList<Integer> al=new ArrayList<Integer>();
	for(int x=0;x<arr.length;x++) {
	al.add(arr[x]);
	}
	System.out.println("请输入你要添加的数字");
	Scanner sc=new Scanner(System.in);
	int num=sc.nextInt();
	//判断数字在数组中的位置
	
	//在对应位置添加元素
	al.add(demo(0,(arr.length)-1,num),num);
	//还原数组
	int[] arr2=new int[al.size()];
	for(int x=0;x<al.size();x++) {
		arr2[x]=al.get(x);
	}
	for (int i : arr2) {
		System.out.print(i+" ");
	}
	
}
private static int demo(int fast,int lest,int num) {
	int[] arr=new int[] {1,5,10,20,21,25};
	if(arr[(fast+lest)/2]>num) {
		if((fast+lest)/2==fast) {
			return fast;
		}else if(arr[fast]>num){
			return fast;
		}
		else{
		if(arr[(fast+lest)/2]>num && arr[(fast+lest)/2-1]<=num) {
			return (fast+lest)/2;
			
		}else {
			lest=(fast+lest)/2;
			return demo(fast,lest,num);
			
		}}
	}else if(arr[(fast+lest)/2]<num){
		if((fast+lest)/2==lest) {
			return fast;
		}else if(arr[lest]<num){
			return lest;
		}else {
		if(arr[(fast+lest)/2]<num && arr[(fast+lest)/2+1]>=num) {
			return (fast+lest)/2+1;
		}else {
			fast=(fast+lest)/2;
			return demo(fast,lest,num);
			
	}}
		
	}else {
		return (fast+lest)/2;
	}


	}

}

